1. Field of the Inventions
The field of invention relate generally to communications switching networks and more particularly to systems and methods for designing, utilizing and upgrading scalable switching networks.
2. Background Information
Switching networks with regular structure have been explored for many years. Conspicuous among them are the so-called fixed radix networks, which typically comprise n stages of rn switching elements with each switching element having a fanin and fanout of r, where r is the radix. The majority of past research has been focused on radix two networks that is where r=2. Coke and Lipovski in “Banyan Network for Partitioning Multiprocessor Systems,” proposed the Banyan network illustrated in FIG. 1B and extended to other radixes such as a radix three network illustrated in FIG. 1C. This network actually finds its origin in the design of fast Fourier Transforms where it is also often termed a butterfly network. Patel in “Performance of Processor-Memory Interconnections for Multiprocessors” proposed the delta network shown in FIG. 1D. The network shown in FIG. 1E is often called a crossover network. Lawrie in “Parallel Processing with a Perfect Shuffle,” uses the network shown in FIG. 1F, known as a perfect shuffle, which is often termed in the art as an Omega network. A nameless radix two network can be found in the bit order preserving fast Fourier transform architecture described in Oppenheim and Schaefer's text, Digital Signal Processing. This network is shown in FIG. 1G and is referred to as a BOP network for the purpose of this disclosure.
These traditional radix networks offer functional connectivity, but lack redundancy and fault tolerance. Many methods and architectures have been developed to extend fixed radix networks to add redundancy and fault tolerance. Hamid, Shiratori and Noguchi in “A new fast control mechanism for Benes rearrangeable interconnection network useful for supersystems,” extend the delta network with a second delta network into an architecture first suggested by Benes in “Permutation Groups, Complexes, and Rearrangeable Connecting Networks,” as shown in FIG. 2A. This can be reconfigured to show two Banyan networks coupled together as shown in FIG. 2B.
Further, Adams and Siegel in “The Extra Stage Cube: A Fault-Tolerant Interconnection Network for Supersystems,” teach the extra stage cube which resembles a Banyan network in FIG. 2C with an extra stage. Through the use of multiplexers 16 and demultiplexers 14, stage 10 and stage 12 can individually be enabled or bypassed giving fault tolerance to the entire network.
Kumar and Reddy in “Augmented shuffle-exchange multistage interconnection networks”, add fault tolerance and path redundancy to a Banyan network offering additional lateral paths for signals to travel which is depicted in FIG. 2D, This augmented shuffle-exchange network (ASEN) increases fault tolerance and path redundancy at the expense of increased path blocking.
Another technique for augmenting fixed radix network designs is by overlaying a second network onto a preexisting design. By this method, the fault tolerance of a network can be increased. The simplest technique is dilation, which is simply the overlaying of the same network on itself. FIG. 3A shows a Banyan network like that depicted in FIG. 1B overlaid on top of a second identical Banyan network. In the traditional design, the external ports are not augmented in the process. However, some designs do incorporate it as shown in FIG. 3B. In either case, the resultant network does increase the ability to tolerate a failure in an internal connection, but fails to compensate for any potential failure in a switching element.
This dilation technique is further refined by overlaying an upside-down version of the same network on top of itself. FIG. 4A depicts a Banyan network like that of FIG. 1B except upside-down. Often in this technique, the connections depicted by the dotted lines are often considered overly redundant and are omitted. The result is the network shown in FIG. 4B. Once again the external ports are usually not augmented, but can be. This new network does compensate for failures in switching elements.
A final extension of multistage interconnection design is the seldom used multidimensional version of the multistage interconnection network. Though not well known in switching applications, multidimensional interconnections are frequently used in signal processing. Specifically, in the design of fast Fourier transforms (FFT) multistage interconnection networks are used. Since fixed radix networks, in particular the butterfly/Banyan, are the essential building blocks of the FFT. Multidimensional extensions of the butterfly are the essential building blocks of multidimensional FFT. This is discussed in great detail in any standard multidimensional signal processing text such as Dudgeon and Mersereau's Multidimensional Signal Processing. 